int aug(int u,int _min)
{
	vis[u]=true;
	if(u==T)
	{
		cost+=dis[S]*_min;
		flow+=_min;
		return _min;
	}
	int ret=0,k;
	for(int i=head[u];~i;i=e[i].next)
	{
		int v=e[i].v;
		if(!e[i].flow||vis[v]||dis[v]-dis[u]+e[i].cost)continue;
		k=aug(v,min(_min-ret,e[i].flow));
		e[i].flow-=k;
		e[i^1].flow+=k;
		ret+=k;
		if(ret==_min)break;
	}
	return ret;
}
bool mdf()
{
	int _min=INF;
	for(int u=S;u<=T;++u)
	{
		if(!vis[u])continue;
		for(int i=head[u];~i;i=e[i].next)
		{
			int v=e[i].v;
			if(!e[i].flow||vis[v])continue;
			_min=min(_min,dis[v]-dis[u]+e[i].cost);
		}
	}
	if(_min==INF)return false;
	for(int i=S;i<=T;++i)
		if(vis[i])
			dis[i]+=_min;
	return true;
}
void zkw()
{
	flow=cost=0;
	memset(dis,0,sizeof(dis));
	do do memset(vis,0,sizeof(vis));
	while(aug(S,INF));
	while(mdf());
	return;
}
